// https://leetcode.cn/problems/max-chunks-to-make-sorted/
// Created by ade on 2022/10/13.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 最笨的方法 代码量大，而且不易维护
    int maxChunksToSorted1(vector<int> &arr) {
        if (arr.size() <= 1) return 1;
        int step = arr[0], num = 0, len = arr.size();
        for (int i = 0; i < len; i++) {
            while (step == 0) {
                num++;
                i++;
                if (i >= len) return num;
                step = arr[i] - i;
            }
            while (step > 0) {
                step--;
                i++;
                if (i == len) {
                    return num + 1;
                }
                int newStep = arr[i] - i;
                if (step == 0) {
                    if (newStep < 0) {
                        num++;
                        if (i + 1 == len) return num;
                        step = arr[i + 1] - i - 1;
                    } else {
                        step = newStep;
                    }
                } else {
                    step = max(step, newStep);
                }
            }
        }
        return num;
    }

    // 思路：每次比较当前最大值和索引值，如果相等，代表可以等分
    int maxChunksToSorted(vector<int> &arr) {
        int maxNum = -1, num = 0;
        for (int i = 0; i < arr.size(); i++) {
            maxNum = max(arr[i], maxNum);
            if (maxNum == i) num++;
        }
        return num;
    }
};

int main() {
    Solution so;
    vector<int> arr = {0, 1, 3, 5, 4, 2};
//    vector<int> arr = {1, 0, 2, 3, 4};
//    vector<int> arr = {1, 2, 0, 3};
//    vector<int> arr = {4, 3, 2, 1, 0};
    int a = so.maxChunksToSorted(arr);
    cout << a << endl;
    return 0;
}